package demo_leetcode_day;

/*
我们得到了一副藏宝图，藏宝图显示，在一个迷宫中存在着未被世人发现的宝藏。
迷宫是一个二维矩阵，用一个字符串数组表示。它标识了唯一的入口（用 'S' 表示），和唯一的宝藏地点（用 'T' 表示）。但是，宝藏被一些隐蔽的机关保护了起来。在地图上有若干个机关点（用 'M' 表示），只有所有机关均被触发，才可以拿到宝藏。
要保持机关的触发，需要把一个重石放在上面。迷宫中有若干个石堆（用 'O' 表示），每个石堆都有无限个足够触发机关的重石。但是由于石头太重，我们一次只能搬一个石头到指定地点。
迷宫中同样有一些墙壁（用 '#' 表示），我们不能走入墙壁。剩余的都是可随意通行的点（用 '.' 表示）。石堆、机关、起点和终点（无论是否能拿到宝藏）也是可以通行的。
我们每步可以选择向上/向下/向左/向右移动一格，并且不能移出迷宫。搬起石头和放下石头不算步数。那么，从起点开始，我们最少需要多少步才能最后拿到宝藏呢？如果无法拿到宝藏，返回 -1 。

示例 1：
输入： ["S#O", "M..", "M.T"]
输出：16
解释：最优路线为： S->O, cost = 4, 去搬石头 O->第二行的M, cost = 3, M机关触发 第二行的M->O, cost = 3, 我们需要继续回去 O 搬石头。 O->第三行的M, cost = 4, 此时所有机关均触发 第三行的M->T, cost = 2，去T点拿宝藏。 总步数为16。
示例 2：
输入： ["S#O", "M.#", "M.T"]
输出：-1
解释：我们无法搬到石头触发机关
示例 3：
输入： ["S#O", "M.T", "M.."]
输出：17
解释：注意终点也是可以通行的。
限制：
1 <= maze.length <= 100
1 <= maze[i].length <= 100
maze[i].length == maze[j].length
S 和 T 有且只有一个
0 <= M的数量 <= 16
0 <= O的数量 <= 40，题目保证当迷宫中存在 M 时，一定存在至少一个 O 。
*/

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Set;

public class demo_20200729 {
    public static void main(String[] args) {
        System.out.println(new Solution().minimalSteps(new String[]{
                "S#O",
                "M..",
                "M.T"
        }));
    }

    static class Solution {
        enum Type {
            // 开始点
            S,
            // 石头点
            O,
            // 机关点
            M,
            // 结束点
            T,
            // 空白
            B,
            // 墙
            W;
        }

        // 节点
        class Node {
            public int x, y;
            public Type type;

            public Node(int x, int y, Type type) {
                this.x = x;
                this.y = y;
                this.type = type;
            }

            public int getX() {
                return x;
            }

            public int getY() {
                return y;
            }

            public Type getType() {
                return type;
            }

            @Override
            public boolean equals(Object o) {
                if (this == o) return true;
                Node node = (Node) o;
                return x == node.x && y == node.y;
            }

            @Override
            public int hashCode() {
                return Objects.hash(x, y);
            }
        }

        // 棋盘
        class Board {
            // 基本
            Node[][] data;
            int xlength = 0;
            int ylength = 0;
            // 各种点
            Node sNode; // 开始点
            Node tNode; // 结束点
            List<Node> oNode = new ArrayList<>(); // 石头点
            List<Node> mNode = new ArrayList<>(); // 机关点

            // 初始化
            Board(String[] maze) {
                // 棋盘初始化
                this.xlength = maze.length;
                this.ylength = maze[0].length();
                this.data = new Node[this.xlength][this.ylength];
                // 遍历，设置点
                for (int i = 0; i < maze.length; i++) {
                    maze[i] = maze[i].replaceAll("\\.", "B").replaceAll("#", "W");
                    for (int j = 0; j < maze[i].length(); j++) {
                        Node node = new Node(i, j, Type.valueOf(String.valueOf(maze[i].charAt(j))));
                        data[i][j] = node;
                        switch (node.type) {
                            case S:
                                this.sNode = node;
                                break;
                            case T:
                                this.tNode = node;
                                break;
                            case O:
                                this.oNode.add(node);
                                break;
                            case M:
                                this.mNode.add(node);
                                break;
                        }
                    }
                }
            }

            // 取得节点
            public Node getNode(int x, int y) {
                return this.data[x][y];
            }
        }

        // 计算
        public int minimalSteps(String[] maze) {
            Board board = new Board(maze);


            pathFinding(board, board.getNode(0,0) , board.getNode(0,2));

            return 1;
        }


        /**
         * 以下寻路相关
         */
        // 路径节点
        class PathNode extends Node implements Comparable<PathNode> {
            public int F; // 计算值
            public int H; // 终点到当前点距离
            public int G; // 起点到当前点距离
            public Node parent;

            public PathNode(Node node) {
                super(node.x, node.y, node.type);
            }

            public PathNode(int x, int y, Type type) {
                super(x, y, type);
            }

            // 计算处理
            public void compute(Node start, Node end) {
                this.H = Math.abs(this.y - end.y) + Math.abs(this.x - end.x);
                this.G = Math.abs(this.y - start.y) + Math.abs(this.x - start.x);
                this.F = this.H + this.G;
            }

            @Override
            public int compareTo(PathNode o) { // 比较时，使用计算结果比较
                return this.F - o.F;
            }
        }

        // 寻路，使用A*方法，寻找最短路径
        private int pathFinding(Board board, Node s, Node e) {
            PathNode start = new PathNode(s);
            PathNode end = new PathNode(e);
            // 两种列表
            PriorityQueue<PathNode> openList = new PriorityQueue<>(); // 使用PriorityQueue，进行排序寻找最小用
            Set<PathNode> closeList = new HashSet<>(); //
            // 追加首节点
            openList.add(start);
            while (!openList.isEmpty()) {
                // 取出节点作为当前节点
                PathNode curNode = openList.poll();
                // System.out.println("当前处理的点(x:"+curNode.x+",y:"+curNode.y+")");
                // 当前节点插入闭合节点（当前节点已处理）
                closeList.add(curNode);
                if (curNode.equals(e)) {
                    break;
                }
                // 四周的点寻找
                for (PathNode nextNode : getRoundNode(board, curNode)) {
                    if (nextNode.type == Type.W || closeList.contains(nextNode)) { // 下一阶段是墙，或者已处理时，跳过
                        continue;
                    }
                    nextNode.compute(s, e);
                    if (!openList.contains(nextNode)) {
                        // 不存在时，追加
                        nextNode.parent = curNode;
                        // 追加到开启列表中
                        openList.add(nextNode);
                    }
                }
            }
            return closeList.size();
        }

        // 寻找节点四周的点
        private List<PathNode> getRoundNode(Board board, PathNode curNode) {
            List<PathNode> nodeList = new LinkedList<>();
            if (curNode.x - 1 >= 0) {
                nodeList.add(new PathNode(board.getNode(curNode.x - 1, curNode.y)));
            }
            if (curNode.y - 1 >= 0) {
                nodeList.add(new PathNode(board.getNode(curNode.x, curNode.y - 1)));
            }
            if (curNode.x + 1 < board.xlength) {
                nodeList.add(new PathNode(board.getNode(curNode.x + 1, curNode.y)));
            }
            if (curNode.y + 1 < board.ylength) {
                nodeList.add(new PathNode(board.getNode(curNode.x, curNode.y + 1)));
            }
            return nodeList;
        }

    }
}
